package com.tgy.algorithm.base;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Stack;

public class _二叉树的序列号与反序列化 {

    public static BiTreeNode generalBiTreeNode() {

        /**
         *              1
         *        2           3
         *          5     6
         *
         */
        BiTreeNode root = new BiTreeNode(1);
        root.left = new BiTreeNode(2);
        root.right = new BiTreeNode(3);
        root.left.right = new BiTreeNode(5);
        root.right.left = new BiTreeNode(6);
        return root;
    }

    public static void biTreeSerialize(BiTreeNode root, LinkedList<Object> list) {


        if (root == null) {
            list.offer(null);
            return;
        }

        list.offer(root.value);
        biTreeSerialize(root.left, list);
        biTreeSerialize(root.right, list);
    }

    public static BiTreeNode biTreeDeserialize(LinkedList<Object> list) {
        if (list.size() == 0) {
            return null;
        }
        BiTreeNode root = getBiTreeNode(list.poll());
        if (root == null) {
            return root;
        }

        root.left = biTreeDeserialize(list);
        root.right = biTreeDeserialize(list);
        return root;
    }

    public static BiTreeNode getBiTreeNode(Object value) {

        if (value == null) {
            return null;
        }
        return new BiTreeNode((Integer) value);
    }

    public static void biTreeLevelSerialize(LinkedList<Object> list, BiTreeNode root) {

        if (root == null) {
            list.offer(null);
            return;
        }

        LinkedList<BiTreeNode> queue = new LinkedList<>();
        // 在加入队列的时候，就加入当前节点的值加入到序列号的队列中
        queue.offer(root);
        list.offer(root.value);
        while (!queue.isEmpty()) {
            BiTreeNode node = queue.poll();
            if (node.left != null) {
                queue.offer(node.left);
                list.offer(node.left.value);
            }else {
                list.offer(null);
            }

            if (node.right != null) {
                queue.offer(node.right);
                list.offer(node.right.value);
            }else {
                list.offer(null);
            }
        }
    }

    public static BiTreeNode biTreeNodeLevelDeserialize(LinkedList<Object> list) {
        if (list == null || list.size() == 0) {
            return null;
        }
        BiTreeNode root = getBiTreeNode(list.poll());
        LinkedList<BiTreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while (!list.isEmpty()) {
            BiTreeNode node = queue.poll();
            node.left = getBiTreeNode(list.poll());
            if (node.left != null) {
                queue.offer(node.left);
            }
            node.right = getBiTreeNode(list.poll());
            if (node.right != null) {
                queue.offer(node.right);
            }
        }

        return root;
    }

    public static void biTreeInOrderSerialize(LinkedList<Object> list,  BiTreeNode root) {

        if (root == null) {
            list.offer(null);
            return;
        }

        biTreeInOrderSerialize(list, root.left);
        list.offer(root.value);
        biTreeInOrderSerialize(list, root.right);
    }

    public static void biTreePostOrderSerialize(LinkedList<Object> list,  BiTreeNode root) {
        if (root == null) {
            list.offer(null);
            return;
        }
        biTreePostOrderSerialize(list, root.left);
        biTreePostOrderSerialize(list, root.right);
        list.offer(root.value);
    }

    public static BiTreeNode biTreeNodeInOrderDeserialize(LinkedList<Object> list) {


        BiTreeNode lefNode = biTreeNodeLevelDeserialize(list);
//        node.left = lefNode;
        BiTreeNode rightNode = biTreeNodeLevelDeserialize(list);

        return null;
    }

    public static void biTreeNodePostOrder(BiTreeNode root) {
        if (root == null) {
            return;
        }

        /**
         *              1
         *        2           3
         *          5     6
         *
         */
        Stack<BiTreeNode> stack = new Stack<>();
        Stack<BiTreeNode> reserveStack = new Stack<>();
        stack.push(root);
        while (!stack.isEmpty()) {
            BiTreeNode node = stack.pop();
            reserveStack.push(node);
            if (node.left != null) {
                stack.push(node.left);
            }

            if (node.right != null) {
                stack.push(node.right);
            }
        }

        while (!reserveStack.isEmpty()) {
            BiTreeNode node = reserveStack.pop();
            System.out.println(node.value);
        }
    }

    public static BiTreeNode biTreeNodePostOrderDeserialize(LinkedList<Object> list) {
        if (list == null || list.size() == 0) {
            return null;
        }
        BiTreeNode root = getBiTreeNode(list.removeLast());
        if (root == null) {
            return root;
        }
        root.right = biTreeNodePostOrderDeserialize(list);
        root.left = biTreeNodePostOrderDeserialize(list);
        return root;
    }

    public static void main(String[] args) {
        LinkedList<Object> list = new LinkedList<>();
        BiTreeNode root = generalBiTreeNode();
//        biTreeSerialize(root, list);
//        biTreeLevelSerialize(list,root);
//        biTreeInOrderSerialize(list,root);
//        System.out.println(list);
//        BiTreeNode biTreeNode = biTreeNodeLevelDeserialize(list);
//        System.out.println(biTreeNode);
//        System.out.println(list);
//        BiTreeNode deRoot = biTreeDeserialize(list);
//        System.out.println(deRoot);
//        biTreeNodePostOrder(root);
        biTreePostOrderSerialize(list, root);
        System.out.println(list);
        BiTreeNode biTreeNode = biTreeNodePostOrderDeserialize(list);
        System.out.println(biTreeNode.value);
    }
}
